home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 050 / madtrb10.arc / HASH.DOC < prev    next >
Encoding:
Text File  |  1985-12-07  |  2.9 KB  |  78 lines
  1. The following is a Pascal assignment that I had in data structures.  It
  2. implements a hash table and linked list for storing data using pointers.  It is
  3. probably of use to you if you want to learn something about chain bucket
  4. hashing and pointers.  Before digging into the code perhaps you want to get
  5. a book on data structures and read up on what hashing is.  Happy computing!!
  6.  
  7.                                                        Chris Maeder
  8.  
  9.  
  10.                     CHAIN BUCKET HASHING ASSIGNMENT
  11.  
  12.                            Data  Structures
  13.                                Fall 1985
  14.  
  15. Write a program to store information about your friends/family/business
  16. associates using a hash table.  The information kept on each person will be
  17. name, birthday, and address.  For each record, hash on name.
  18.  
  19. Use this hash function:
  20.  
  21.      Add the ordinal values of every character in the name but do not include
  22.      any blanks.  (It is OK to include the comma.)  Then use the Mod function
  23.      to keep the result in the range 0 to 12 (i.e. dimension the hash table
  24.      from 0 to 12).  The hashtable must be an array of pointers, not an array
  25.      of records.  Use chain bucket hashing to handle collisions.  Each chain
  26.      must be kept in sorted order to facilitate searching.
  27.  
  28. Example input file:
  29.  
  30.      I Jones,Jack 07/20 1918 University Ave.
  31.      I Smith,Bob 09/02 105 Langdon St.
  32.      S Jones,Jack
  33.      S Becker,Ann
  34.      I Dodge,Ken 08/18 2102 Kendall Ave.
  35.      D Smith,Bob
  36.  
  37. An input record will start with I (for insert), S (for search), or D (for
  38. delete).  Note the formats for S and D differ from I.  Assume each input
  39. record is correct in its number and type of fields -- no error checking needed
  40. here.
  41.  
  42.      I  means to insert a person into the hash table.  Remember to keep each
  43.         linked list sorted in ascending order.
  44.  
  45.      S  means to search for that person's record and to print it out.
  46.  
  47.      D  means to delete that person from the hash table (also dispose of the
  48.         node).
  49.  
  50. Notes:
  51.  
  52.      For S and D, it is possible the record will not exist in the table.
  53.  
  54.      The name field is of the form lastname,firstname with no blank in between.
  55.      Consider this to be one field.
  56.  
  57.      Fields are separated by one blank.
  58.  
  59.      The maximum name size is 16 characters, birthday takes 5 characters, and
  60.      the maximum address size is 25 characters (read until end of line).
  61.  
  62. Output:
  63.  
  64.      Print a message for each input command stating what was done.  Include
  65.      printing the input values with labels.  After this, print the hash table
  66.      and its contents in the following manner:
  67.  
  68.                 Table Index          Names hashing to this index
  69.                 -----------          ---------------------------
  70.  
  71.                      0               Jones,Jack
  72.                                      Smith,Bob
  73.  
  74.                      1               Becker,Ann
  75.  
  76.                      2               No one
  77.  
  78.                     etc.